import java.util.ArrayList;

/**
 * @ClassName Offer24
 * @Description 剑指 Offer 24. 反转链表
 * @Author clockTown
 * @Date 2021/8/13 16:39
 * @Version 1.0
 */
class Offer24 {
}

/**
 * v0 使用 ArrayList存储链表节点，最后逆序重组链表
 */
class Offer24V0 {
    public ListNode reverseListV0(ListNode head) {

        ArrayList<ListNode> list = new ArrayList<>();
        ListNode curNode = head;
        //先遍历到链表末尾
        while (curNode != null) {
            list.add(curNode);
            curNode = curNode.next;
        }
        ListNode res = new ListNode(0);
        curNode = res;

        for (int i = list.size() - 1; i >= 0; i--) {
            curNode.next = list.get(i);
            curNode = curNode.next;
        }
        curNode.next = null;
        return res.next;
    }
}

/**
 * v1 双指针
 */
class Offer24V1 {
    public ListNode reverseList(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null) {
            // 暂存后继节点 cur.next
            ListNode tmp = cur.next;
            // 修改 next 引用指向
            cur.next = pre;
            // pre 暂存 cur
            pre = cur;
            // cur 访问下一节点
            cur = tmp;
        }
        return pre;
    }
}

/**
 * 递归
 */
class Offer24V2 {
    public ListNode reverseList(ListNode head) {
        // 调用递归并返回
        return recur(head, null);
    }

    private ListNode recur(ListNode cur, ListNode pre) {
        // 终止条件
        if (cur == null) {
            return pre;
        }
        // 终止条件
        ListNode res = recur(cur.next, cur);
        // 修改节点引用指向
        cur.next = pre;
        // 返回反转链表的头节点
        return res;
    }
}